package leetcode_1201_1300;

import java.util.ArrayDeque;
import java.util.Deque;

public class LeeCode_1254 {
    public static void main(String[] args) {
        System.out.println(closedIsland(new int[][]{{1, 1, 1, 1, 1, 1, 1, 0}, {1, 0, 0, 0, 0, 1, 1, 0}, {1, 0, 1, 0, 1, 1, 1, 0}, {1, 0, 0, 0, 0, 1, 0, 1},
                {1, 1, 1, 1, 1, 1, 1, 0}}));
    }
    private static int closedIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] vis = new boolean[m][n];
        int[][] dirs = new int[][]{{0, 1},{0,-1},{1,0},{-1,0}};
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0 && !vis[i][j] && i != 0 && i != m - 1 && j != 0 && j != n - 1){
                    Deque<int[]> deque = new ArrayDeque<>();
                    deque.add(new int[]{i, j});
                    vis[i][j] = true;
                    boolean flag = false;
                    while (!deque.isEmpty()){
                        int[] p = deque.pop();
                        int x = p[0], y = p[1];
                        vis[x][y] = true;
                        for (int[] dir : dirs) {
                            int nx = x + dir[0], ny = y + dir[1];
                            if (nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] == 1 || vis[nx][ny]){
                                continue;
                            }
                            if (nx == 0 || nx == m - 1 || ny == 0 || ny == n - 1){
                                flag = true;
                            }
                            deque.add(new int[]{nx, ny});
                        }
                    }
                    if (!flag)
                        ans++;
                }
            }
        }
        return ans;
    }
}